TNotes.leetcode

Appearance

0705. 设计哈希集合【简单】

0705. 设计哈希集合【简单】 ​

1. 📝 题目描述 ​

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

  • void add(key) 向哈希集合中插入值 key。
  • bool contains(key) 返回哈希集合中是否存在这个值 key。
  • void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例：

txt
输入：
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出：
[null, null, null, true, false, null, true, null, false]

解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False，（未找到）
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // 返回 False，（已移除）

提示：

  • 0 <= key <= 10^6
  • 最多调用 10^4 次 add、remove 和 contains

2. 🎯 s.1 - 分离链接法（拉链法） ​

js
// 使用分离链接法（拉链法）实现哈希集合
var MyHashSet = function () {
  this.capacity = 1024 // 2^10 初始桶数量（2 的幂更利于位运算）
  this.buckets = Array.from({ length: this.capacity }, () => [])
}

/**
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.add = function (key) {
  const idx = this._hash(key)
  const bucket = this.buckets[idx]
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i] === key) return // 已存在，直接返回
  }
  bucket.push(key)
}

/**
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.remove = function (key) {
  const idx = this._hash(key)
  const bucket = this.buckets[idx]
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i] === key) {
      bucket.splice(i, 1)
      return
    }
  }
}

/**
 * @param {number} key
 * @return {boolean}
 */
MyHashSet.prototype.contains = function (key) {
  const idx = this._hash(key)
  const bucket = this.buckets[idx]
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i] === key) return true
  }
  return false
}

// 简单哈希函数：按容量取模（key 范围 0..1e6）
MyHashSet.prototype._hash = function (key) {
  return key & (this.capacity - 1) // 等价于 key % capacity（当 capacity 为 2 的幂）
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * var obj = new MyHashSet()
 * obj.add(key)
 * obj.remove(key)
 * var param_3 = obj.contains(key)
 */
  • 时间复杂度：
    • add：平均 O(1)，最坏 O(k)（桶中链长）
    • remove：平均 O(1)，最坏 O(k)
    • contains：平均 O(1)，最坏 O(k)
  • 空间复杂度：O(B+N)，其中 B 为桶数量，N 为集合中元素数量

算法思路：

  • 使用固定容量的桶数组，每个桶用数组作为链表来存放冲突元素
  • 哈希函数使用按容量取模（容量取 2 的幂）便于位运算加速
  • add 检查桶内是否已存在，避免重复；不存在则追加
  • remove 在线性扫描命中后移除对应元素
  • contains 在线性扫描命中后返回 true，否则返回 false

Discussions